public class Solution1043 {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int[][] f=new int[arr.length][arr.length];
        for (int i=0;i< arr.length;i++){
            f[i][i]=arr[i];
            for (int j=i+1;j<arr.length;j++){
                f[i][j]=Math.max(f[i][j-1],arr[j]);
            }
        }
        int[] g=new int[arr.length+1];
        for (int i=1;i<=arr.length;i++){
            for (int j=1;j<=k;j++){
                if (i-j<0){
                    break;
                }
                g[i]=Math.max(g[i],g[i-j]+f[i-j][i-1]*j);
            }
        }
        return g[arr.length];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1043().maxSumAfterPartitioning(new int[]{1,15,7,9,2,5,10},3));
    }
}
